package data_structure;

import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 跳跃表的简易实现，
 * 仅仅测试遍历循环的测试
 */
public class demo_01_SkipList {
    public static void main(String[] args) throws Exception {
        SkipList skipList = new SkipList(12345678);

        long time01 = System.nanoTime();
        System.out.println("遍历法："+skipList.getNode(987654).intValue()+",用时："+(System.nanoTime()-time01));

        long time02 = System.nanoTime();
        System.out.println("跳跃表："+skipList.getNodeBySkipList(987654)+",用时："+(System.nanoTime()-time02));

    }
}


class SkipList {
    List<BigDecimal> listNode = new ArrayList<BigDecimal>();
    List<BigDecimal> SkipListNode = new ArrayList<BigDecimal>();
    SkipList(int number){
        for(int i = 0;i<number;i++){
            listNode.add(new BigDecimal(i));
            if(i % 100000 == 0){
                SkipListNode.add(new BigDecimal(i));
            }
        }
    }
    // 遍历寻找节点
    public BigDecimal getNode(int number){
        for (BigDecimal node : this.listNode){
            if (node.compareTo(new BigDecimal(number)) == 0){
                return node;
            }
        }
        return null;
    }
    // 遍历寻找节点--通过跳跃表
    public BigDecimal getNodeBySkipList(int number){
        // 先循环跳跃表
        for(int i = 0;i<SkipListNode.size();i++){
        BigDecimal node = SkipListNode.get(i);
            if (node.compareTo(new BigDecimal(number)) >= 0){
                // 在循环列表
                for (int j = i; j>0; j++){
                    if(listNode.get(j).compareTo(new BigDecimal(number)) == 0){
                        return listNode.get(j);
                    }
                }
            }
        }
        return null;
    }
}
